package day003;

import java.util.LinkedList;
import java.util.Queue;

//完全二叉树
public class Code03_IsCBT {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static boolean isCBT(Node head){
        if(head == null){
            return true;
        }
        boolean leafNode = false;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        Node l ,r;
        while(!queue.isEmpty()){
            head = queue.poll();
            System.out.println(head.value);

            l = head.left;
            r = head.right;

//            if(
//                    (leafNode && (l != null || r != null))
//                            ||
//                    (l == null && r != null)
//            ){
//                return false;
//            }

            if(l == null && r != null){
                return false;
            }
            if(leafNode && (l != null || r != null)){
                return false;
            }

            if(head.left != null){
                queue.add(head.left);
            }
            if(head.right != null){
                queue.add(head.right);
            }
            if(head.left == null || head.right == null){
                leafNode = true;
            }
        }
        return true;
    }

    public static void main(String[] args) {

        Node n6 = new Node(6);
        Node n5 = new Node(5);
        Node n4 = new Node(4);
        Node n3 = new Node(3,n6,null);
        Node n2 = new Node(2,n4, n5);
        Node n1 = new Node(1,n2,n3);

        System.out.println(isCBT(n1));
    }
}
